﻿// 0814train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;

/*
 1判断是否在边界内 2是否访问过 3是否陆地==1
 */
class DFSClass
{
public:
    DFSClass()
    {
	    
    }
    void DFS(vector<vector<int>>& grid, vector<vector<int>>& checked_grid, int r, int c)
    {
        int row_size = grid.size();
        int col_size = grid[0].size();

        vector<vector<int>>Direction = { {-1,0},{1,0},{0,-1},{0,1} };
        //标记已访问
        checked_grid[r][c] = true;
        area_count += 1;

        for (auto& dir_vec : Direction)
        {
            int curr_r = r + dir_vec[0];
            int curr_c = c + dir_vec[1];

            bool if_row = curr_r >= 0 && curr_r < row_size;
            bool if_col = curr_c >= 0 && curr_c < col_size;

            if (if_row && if_col)
            {
                bool if_visited = checked_grid[curr_r][curr_c];
                bool if_available = grid[curr_r][curr_c] == 1;

                if (!if_visited && if_available)
                {
                    DFS(grid, checked_grid, curr_r, curr_c);
                }

            }

        }
        //DFS
    }

    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        //1记录row_size, col_size
        //2初始化checked_grid
        //3双重循环 4DFS

        int row_size = grid.size();
        int col_size = grid[0].size();

        vector<int>checked_status(col_size, false);
        vector<vector<int>>checked_grid(row_size, checked_status);

        int result = 0;
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                int curr_status = grid[r][c];
                bool curr_visited = checked_grid[r][c];
                if (curr_status==1 && !curr_visited)
                {
                    DFS(grid, checked_grid, r, c);
                    result = max(result, area_count);
                    area_count = 0;
                }
            }
        }

        return result;
        //maxAreaOfIsland
    }
private:
    int area_count = 0;

};

/*
 grid = [
 [0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
 */

/*
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
 */

class DFSClass02
{
public:
    void DFS(vector<vector<int>>&grid, vector<vector<bool>>&checked_grid, int r, int c)
    {
        //1是否越界 2是否==1 3是否未访问过
        checked_grid[r][c] = true;
        int row_size = grid.size();
        int col_size = grid[0].size();

        vector<vector<int>>Direction = {
            {-1,0},{1,0} ,{0,-1} ,{0,1},
            {-1,-1},{-1,1} ,{1,-1} ,{1,1},
        };

        for (auto&dir_vec:Direction)
        {
            int curr_r = r + dir_vec[0];
            int curr_c = c + dir_vec[1];

            bool if_r = curr_r >= 0 && curr_r < row_size;
            bool if_c = curr_c >= 0 && curr_c < col_size;

            if (if_r&&if_c)
            {
                bool if_visited = checked_grid[curr_r][curr_c];
                bool if_available = grid[curr_r][curr_c] == 1;

                if (!if_visited && if_available)
                {
                    DFS(grid, checked_grid, curr_r, curr_c);
                }
            }
        }
	    //DFS------
    }

    void solve02(vector<vector<int>>& grid)
    {
        //1记录row_size, col_size
        //2checked_grid
        //3双重循环 4dfs
        int row_size = grid.size();
        int col_size = grid[0].size();

        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked_grid(row_size, checked_status);

        int result = 0;
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                int curr_status = grid[r][c];
                bool curr_visited = checked_grid[r][c];

                if (curr_status==1 && !curr_visited)
                {
                    DFS(grid, checked_grid, r, c);
                    result += 1;
                }

            }
        }
        cout << result;
        //solve02------
    }

private:

};


/*
 给你一个由 '0'（空地）、'1'（银矿）、'2'（金矿）组成的的地图，
 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。
假设银矿价值 1 ，金矿价值 2 ，请你找出地图中最大价值的矿堆并输出该矿堆的价值。

22220
00000
00000
01111
 */
class DFSClass03
{
public:
    void DFS(vector<vector<int>>& grid, vector<vector<bool>>&checked_grid, int r, int c)
    {
        int row_size = grid.size();
        int col_size = grid[0].size();

        //标记已访问
        checked_grid[r][c] = true;
        //更新获取的价值
        curr_count += grid[r][c];

        vector<vector<int>>Direction = { {-1,0},{1,0},{0,-1},{0,1}};

        //1是否越界 2是否可访问 3是否可到达
        for (auto&dir_vec:Direction)
        {
            int curr_r = r + dir_vec[0];
            int curr_c = c + dir_vec[1];

            bool if_curr_r = curr_r >= 0 && curr_r < row_size;
            bool if_curr_c = curr_c >= 0 && curr_c < col_size;

            if (if_curr_r&&if_curr_c)
            {
                bool if_visited = checked_grid[curr_r][curr_c];
                bool if_available = grid[curr_r][curr_c] > 0;

                //未访问+可到达
                if (!if_visited && if_available)
                {
                    DFS(grid, checked_grid, curr_r, curr_c);
                }

            }

            //for------
        }


        //DFS------
    }

    void solve03(vector<vector<int>>&grid)
    {
        int row_size = grid.size();
        int col_size = grid[0].size();

        //1初始化checked_grid
        //2双重循环 3DFS
        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked_grid(row_size, checked_status);

        //更新最大价值
        int result = 0;
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                int curr_status = grid[r][c];
                bool curr_visited = checked_grid[r][c];
                if (!curr_visited && curr_status>0)
                {
                    DFS(grid, checked_grid, r, c);
                    result = max(result, curr_count);
                    curr_count = 0;
                }
            }
        }
        cout << result;
        //solve03------
    }
private:
    int curr_count = 0;
};


int main()
{
    /*
    22220
	00000
	00000
	01111
     */
	{
        //vector<int>vec1 = { 2,2,2,2,0 };
        //vector<int>vec2 = { 0,0,0,0,0 };
        //vector<int>vec3 = { 0,0,0,0,0 };
        //vector<int>vec4 = { 0,1,1,1,1 };

        //vector<vector<int>>grid = { vec1 ,vec2,vec3,vec4 };

        vector<vector<int>>grid;
        string input;
        while (getline(cin, input))
        {
            if (input.empty())
            {
                break;
            }
            int input_size = input.size();
            vector<int>oh_vec;
            for (int i=0; i<input_size; i++)
            {
                int curr_num = input[i] - '0';
                oh_vec.push_back(curr_num);
            }
            grid.push_back(oh_vec);
        	//while------
        }
        //for (auto&oh_vec:grid)
        //{
	       // for (auto&num:oh_vec)
	       // {
        //        cout << num << ' ';
	       // }
        //    cout << '\n';
        //}

        DFSClass03 dfs_class;
        dfs_class.solve03(grid);

        return 0;
	}

    /*
    3 3
	1 0 1
	0 1 0
	1 0 1
     */
	{
        //vector<int>vec1 = { 1,1,0,0 };
        //vector<int>vec2 = { 0,0,0,1 };
        //vector<int>vec3 = { 0,0,1,1 };
        //vector<int>vec4 = { 1,1,1,1 };
        //vector<vector<int>>grid = { vec1, vec2, vec3, vec4 };
        int row_size, col_size;
        cin >> row_size >> col_size;
        vector<vector<int>>grid(row_size, vector<int>(col_size));
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];
            }

        }

        DFSClass02 dfs_class;
        dfs_class.solve02(grid);


        return 0;
	}

    vector<int>vec1 = { 0,0,1,0,0,0,0,1,0,0,0,0,0 };
    vector<int>vec2 = { 0,0,0,0,0,0,0,1,1,1,0,0,0 };
    vector<int>vec3 = { 0,1,1,0,1,0,0,0,0,0,0,0,0 };
    vector<int>vec4 = { 0,1,0,0,1,1,0,0,1,0,1,0,0 };
    vector<int>vec5 = { 0,1,0,0,1,1,0,0,1,1,1,0,0 };
    vector<int>vec6 = { 0,0,0,0,0,0,0,0,0,0,1,0,0 };
    vector<int>vec7 = { 0,0,0,0,0,0,0,1,1,1,0,0,0 };
    vector<int>vec8 = { 0,0,0,0,0,0,0,1,1,0,0,0,0 };
    vector<vector<int>>grid = { vec1,vec2,vec3,vec4, vec5,vec6,vec7,vec8 };

    DFSClass dfs_class;
    cout << dfs_class.maxAreaOfIsland(grid);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
